'''
    分析树用于表示诸如句子或数学表达式的真实世界构造。
        - 如何从完全括号的数学表达式构建分析树。-->表达书用树存储
        - 如何评估存储在分析树中的表达式。     -->树中表达式分析
        - 如何从分析树中恢复原始数学表达式。   -->和二差不多
'''

# 利用树解决一些真正的问题
from Tree.TraverseTree import printexp, postordereval

'''
    现在我们将一个表达式存储成树形结构：定义规则如下：
        - 如果当前符号是 `'('`，添加一个新节点作为当前节点的左子节点，并下降到左子节点。(说明要新加一个表达式)
        - 如果当前符号在列表 `['+'，' - '，'/'，'*']` 中，请将当前节点的根值设置为由当前符号表示的运算符。 
            添加一个新节点作为当前节点的右子节点，并下降到右子节点。
        - 如果当前符号是数字，请将当前节点的根值设置为该数字并返回到父节点。
        - 如果当前令牌是 `')'`，则转到当前节点的父节点。
    上面说明我们需要跟踪当前节点和当前节点的父节点，子节点好获取，但是父节点有点复杂，方法是采用栈的方法。
'''

from Stack.Stack import Stack
from BinaryTree import BinaryTree
import operator
from TraverseTree import *

def buildParseTree(fpexp):  # 传入数学表达式
    fplist = fpexp.split()  # 按照空格符划分
    pStack = Stack()    # 栈
    eTree = BinaryTree('')
    pStack.push(eTree)
    currentTree = eTree #当前树

    for i in fplist:
        if i == '(':
            currentTree.insertLeft('')
            pStack.push(currentTree)
            currentTree = currentTree.getLeftChild()
        elif i not in ['+','-','*','/',')']:    # 是数字
            currentTree.setRootVal(int(i))
            parent = pStack.pop()
            currentTree = parent

        elif i in ['+','-','*','/']:
            currentTree.setRootVal(i)
            currentTree.insertRight('') #添加右子树
            pStack.push(currentTree)
            currentTree = currentTree.getRightChild()

        elif i == ')':
            currentTree = pStack.pop()
        else:
            raise ValueError
    return eTree

# 现在我们计算树中的结果.思路就是读取树的根节点，检查左右节点是否都为空，为空则为叶子节点。返回根值就可以，不为空则需要递归调用求取左右子树的值。
# 这边需要考虑如何根据运算符进行相应的运算，这里用了高级的方法，考虑学习
# operator模块可以通过operator.add进行算法相加等等。反正就是将运算符转成了文字形式
def evaluates(parseTree):
    opers = {'+':operator.add,'-':operator.sub,'*':operator.mul,'/':operator.truediv}

    leftc = parseTree.getLeftChild()
    rightc = parseTree.getRightChild()

    if leftc and rightc:
        fn = opers[parseTree.getRootVal()]
        return fn(evaluates(leftc),evaluates(rightc))
    else:
        return parseTree.getRootVal()


pt = buildParseTree("( ( 10 + 5 ) * 3 )")
print(printexp(pt))     # 打印出来就是都含有括号了
print(postordereval(pt))
print(evaluates(pt))


